package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

public class ThreeSumClosest {

    /**
     * 双指针
     * 先对元素进行升序排列，顺序遍历元素
     * 然后就转变为求两数和与（target-nums[i]）最接近的值，
     * 这时候采用双指针，
     * 1. 当和大于目标值时，右边移动，
     * 2. 当和小于目标值时，左边移动，
     * 3. 当和等于目标值时，直接返回0.
     * 4. 当左边和右边无法移动时，返回最接近的值。
     *
     * @param nums
     *  3 <= nums.length <= 10^3
     * -10^3 <= nums[i] <= 10^3
     * @param target
     *  -10^4 <= target <= 10^4
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int res = Integer.MAX_VALUE, minSub = Integer.MAX_VALUE;
        for (int i = 0; i < len - 2; ++i){
            // 去除重复计算
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int j = i + 1;
            int k = len - 1;
            int t = target - nums[i];
            while (j < k){
                int sub = t - (nums[j] + nums[k]);
                if (minSub > Math.abs(sub)){
                    minSub = Math.abs(sub);
                    res = target - sub;
                }
                PrintUtils.println(i, j, k);
                if (sub > 0){
                    j++;
                }else if(sub < 0) {
                    k--;
                } else {
                    return target;
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{-100,-98,-2,-1};
        int target = -101;
        int i = new ThreeSumClosest().threeSumClosest(nums, target);
        System.out.println(i);
        Assert.isTrue(i == -101);
    }

}
